\section*{D\'ia 29-Mayo-2012}
\section{Introducci\'on}

\subsection{Aprendizaje por refuerzos (definici\'on)}

El aprendizaje por refuerzos trata con el problema de un agente que se enfrenta a un ambiente desconocido que le provee una se\~nal de refuerzo (premios y castigos) y debe aprender a realizar acciones que maximicen el refuerzo obtenido. Lo podemos pensar como el problema de ``toma de decisiones secuenciales''.

\begin{figure}[htb]
\centering
\label{fig:rl}
\includegraphics{rl.pdf}
\caption{Aprendizaje por refuerzos - esquema}
\end{figure}

$$s_t + a_t \xrightarrow{\text{lleva a}} (s_{t+1}, r_{t+1})$$

\begin{description} \itemsep1pt \parskip0pt \parsep0pt
	\item[s:] estado
	\item[a:] acci\'on
	\item[r:] refuerzo
\end{description}

\subsection{Funci\'on objetivo}

Buscando maximizar el refuerzo nos encontrarmos con distintos posibles escenarios.

\subsection{Horizonte finito}

\begin{tabular}{>{\centering}p{3cm}p{5cm}}
\ \newline\ \newline \includegraphics[width=3cm]{day01-horizonteFinito.pdf} \newline H nodos & 
	$$V = E\Big(\sum_{t=0}^H r_t\Big)$$\\
\end{tabular}

\subsection{Horizonte infito}

\begin{tabular}{>{\centering}p{5.5cm}p{10cm}}
\ \newline\ \newline \includegraphics[width=5.5cm]{day01-horizonteInfinito.pdf} & 
	$$V = \sum_{t=0}^\infty \gamma^t r_t = r_0 + \gamma r_1 + \gamma^2 r_2 + \ldots$$ $$0 \leq \gamma < 1$$ \\ 
\end{tabular}

$\gamma$: funci\'on de descuento.

Si el refuerzo m\'aximo en el ambiente es $R_{max}$, $V \leq \frac{R_{max}}{1-\gamma}$

\subsection{Average Reward}

Quiero en promedio estar bien.

$$V = \lim_{h \to{+}\infty}{E\Big(\frac{1}{h} \sum_{t=0}^h r_t\Big)}$$

\section{Problema de los K-Bandidos}

\url{http://en.wikipedia.org/wiki/Multi-armed_bandit}

Proviene de las m\'aquinas tragamonedas. Se llama bandido a cada palanca. Cada palanca te da
una recompensa (o no) con una probabilidad que le es propia. Se debe aprender las probabilidades de las palancas para elegir la mejor. 

\fbox{
\begin{minipage}{14 cm}
\textbf{Dilema Exploraci\'on/Explotaci\'on} \\

?`Hasta cu\'ando exploro para decidirme? ?`Cu\'anto exploto la informaci\'on que tengo hasta ahora?
%\begin{description}
%	\item[Caso finito:] lo mejor es explotar
%	\item[Caso infinito:] lo mejor es explorar
%\end{description}

%\small{Esto s\'olo tiene sentido cuando juego por mucho tiempo}
\end{minipage}
}

\subsection{Estrategias de elecci\'on}

\subsubsection{Goloso}

Juego una vez a cada una y elijo la mejor para siempre.

\subsubsection{$\mathcal{E}$-Goloso}

En lugar de elegir la mejor siempre, elijo:
\begin{itemize}
	\item con probabilidad $\mathcal{E}$ elijo 1 al azar
	\item con probabilidad $(1-\mathcal{E})$ elijo la que creo que hasta ahora es mejor
\end{itemize}

\subsubsection{SoftMax}

En lugar de elegir el m\'aximo tomo uno que no sea tan bueno, pero que no sea malo.

\[ P(A) = \frac{e^{\beta V(A)}}{\sum_{i \in brazos} e^{\beta V(i)}}  \]

Al par\'ametro $\beta$ se lo llama temperatura. Si es alta, potencia los brazos de valor m\'aximo, se aproxima a una pol\'itica golosa. Si es baja, explora con probabilidad uniforme. Conviene
empezar con un $\beta$ chico, ya que lo hace equiprobable e ir agrand\'andolo al sumar
experiencia.

\subsubsection{Estimaci\'on de intevalos}

Para cada brazo estimo una media y un intervalo de confianza. Elijo siempre el brazo con el intervalo de confianza m\'as alto. Cada vez que elijo un brazo, el intervalo de confianza se achico porque tengo una muestra m\'as. 

\subsubsection{Matching de probabilidad}

Consiste en elegir proporcionalmente al valor de cada brazo. Es lo que se observa que hacen muchas especies animales. Quiz\'as tiene sentido en ambientes no estacionarios.

\subsection{Evaluaci\'on de algoritmos}

El costo de los algoritmos que intentan resolver un problema se puede medir en 

\begin{description}
	\item[Costo computacional] cu\'anto tengo que computar entre experiencia y experiencia (tirada de brazo).
	\item[Costo de experiencia] cu\'antas veces tengo que tirar de un brazo para saber c\'omo resolver el problema
\end{description}

\section{Aprendizaje guiado por error (Rescorla \& Wagner, 1972)}

Sea $V(Palanca)$ el valor esperado que da una palanca.

Se define $\Delta = (R-V)$ como el error de predicci\'on, donde $R$ es la recompensa obtenida y $V$ la esperada.

Calculamos $V_{t+1} = V_t + \alpha \Delta$ con $0\leq \alpha < 1$. $\alpha$ es el factor de aprendizaje, expresa cu\'anto conf\'ia en lo que sucedi\'o en el tiempo actual y cu\'anto en la historia.

El problema que no resuelve este m\'odelo es el de refuerzos diferidos, en los cuales hay que tomar m\'as de una
decisi\'on para llegar a un refuerzo.

\section{Proceso de decisi\'on de Markov (MDP)}

Se define con un aut\'omata

\[ < S, A, T, R, \gamma >\]

\begin{description} \itemsep1pt \parskip0pt \parsep0pt
	\item[S:] conjunto de estados
	\item[A:] conjunto de acciones
	\item[T:] funci\'on de transici\'on
	\item[R:] funci\'on de refuerzos
	\item[$\gamma$:] funci\'on de descuento
\end{description}

$T(s, a, s') = P(s'|s,a)$ es la probabilidad de llegar a $s'$ estando en $s$ y tomando la acci\'on $a$.
$R(s, a) = E(r|s,a)$ es el refuerzo inmediato esperado por estar en $s$ y tomar $a$.

Est\'as dos anteriores son definidas por el mundo.

Lo que define el agente es la pol\'itica ($\pi$) que va a seguir.

Entonces, $\pi(s) = a$ quiere decir que siguiendo la pol\'itica $\pi$ desde el estado $s$ debo tomar
la acci\'on $a$.

Calculamos el valor para una pol\'itica:

\[V^\pi(s) = E [ r_0 + \gamma r_1 + \gamma^2 r_2 + \ldots] \]

O en su versi\'on recursiva (ecuaci\'on de Bellman):

\[V^\pi(s) = R(s, \pi(s)) + \gamma \sum_{s'} [ T(s,\pi(s), s') . V^\pi(s')] \]   


\fbox{
\begin{minipage}{14 cm}
\textbf{Familia de Soluciones} 

Los podemos dividir en 2 tipos de soluciones:
\begin{itemize}
	\item Model-based: las que adquieren experiencia al principio para poder estimar R y T
	\item Model-free: las que estiman V sin conocer R y T
\end{itemize}

\end{minipage}
}

\section{Metodo  iterativo (conociendo \emph{todo} el ambiente, o sea, dado un MDP)}

Value iteration calcula el valor de cada estado bajo la pol\'itica \'optima.

\begin{algorithm}[H]
\caption{Value Iteration}\label{val-iter}
\begin{algorithmic}[1]
%~ \Procedure{Value Iteration}{$V$}\Comment{The g.c.d. of a and b}
%~ \Procedure{Value Iteration}{}
\State $V(s) \gets 0$ \Comment{Inicializo los estados}
\State $\Delta \gets 0$
\Repeat
    \ForEach {$s \in S$}
        \State $v \gets V(s)$
        \State $V(s) \gets \max_a [ R(s,a) + \gamma \sum_{s'} T(s,a,s') \times V(s')]$
        \State $\Delta \gets \max (\Delta, |v-V(s)|)$
    \EndFor
\Until $\Delta < \mathcal{E}$
%~ \EndProcedure
\end{algorithmic}
\end{algorithm}


\subsection{Elecci\'on de la pol\'itica}

\[\pi = argmax_a(R(s, a) + \gamma \sum_{s'} T(s, a, s') . V(s')] \]